package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DivideConquer;
import cn.pugle.oj.catalog.DynamicProblem;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * https://leetcode.com/problems/longest-palindromic-substring
 * <p>
 * java的数组和list, 我要吐了
 * <p>
 * AC了, 但是  528 ms, faster than 6.14%
 *
 * @author tzp
 * @since 2020/9/12
 */
public class LC5 implements DynamicProblem, DivideConquer {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        List<List<String>> cache = new ArrayList<>(Collections.nCopies(s.length(), null));
        return re(s, 0, s.length() - 1, cache);
    }

    public static String safeGet(List<List<String>> cache, int i, int j) {
        List<String> strings = cache.get(i);
        if (strings != null) {
            return strings.get(j);
        } else {
            return null;
        }
    }

    public static void safeSet(List<List<String>> cache, int i, int j, String s) {
        List<String> strings = cache.get(i);
        if (strings == null) {
            strings = new ArrayList<>(Collections.nCopies(cache.size(), null));
            cache.set(i, strings);
        }
        strings.set(j, s);
    }

    public String re(String s, int start, int end, List<List<String>> cache) {
        String s1 = safeGet(cache, start, end);
        if (s1 != null) {
            return s1;
        }
//        System.out.println("cal " + start + " " + end);
        if (start == end) {
            String s2 = s.substring(start, end + 1);
            safeSet(cache, start, end, s2);
            return s2;
        }
        if (start == end - 1) {
            if (s.charAt(start) == s.charAt(end)) {
                String s2 = s.substring(start, end + 1);
                safeSet(cache, start, end, s2);
                return s2;
            } else {
                String s2 = s.substring(start, start + 1);
                safeSet(cache, start, end, s2);
                return s2;
            }
        }

        String childMax = re(s, start + 1, end - 1, cache);
        if (s.charAt(start) == s.charAt(end) && (childMax.length() == end - start - 1)) {
            String s2 = s.substring(start, end + 1);
            safeSet(cache, start, end, s2);
            return s2;
        }

        String childMax1 = re(s, start + 1, end, cache);
        if (childMax1.length() > childMax.length()) {
            childMax = childMax1;
        }
        String childMax2 = re(s, start, end - 1, cache);
        if (childMax2.length() > childMax.length()) {
            childMax = childMax2;
        }

        safeSet(cache, start, end, childMax);
        return childMax;
    }

    public static void main(String[] args) {
        System.out.println(new LC5().longestPalindrome(""));
        System.out.println(new LC5().longestPalindrome("bbbab"));
//        System.out.println(new LC5().longestPalindrome("civilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth"));
    }
}
